// https://leetcode.cn/problems/sort-colors/

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
		// 插入 不断的和左侧对比，如果比左边小，则做交换
		// sortInsert(nums);
		
		// 快速
		// sortQuick(nums, 0, nums.size() - 1);
		
		// 冒泡
		// sortBubble(nums);
		
		// 选择
		sortSelect(nums);
		
    }
	
	void sortInsert(vector<int>& nums){
		int len = nums.size();
		for(int i = 1; i < len; i++){
			int j = i;
			while(j > 0){
				if(nums[j] < nums[j - 1]){
					swap(nums[j], nums[j - 1]);
					j--;
				}else{
					break;
				}
			}
		}
	}
	
	void sortQuick(vector<int>& nums, int left, int right){
		if(left > right) return;
		int start = left;
		int end = right;
		int base = nums[left];
		// cout << "lefts:" << left << ",right:" << right << endl;
		while(start < end){
			while(nums[end] <= base && start < end){
				end--;
			}
			while(nums[start] >= base && start < end){
				start++;
			}
			//cout << "start:" << start << " " << end << " " << nums[start] << " " << nums[end] << endl;
			if(start < end){
				swap(nums[start], nums[end]);
			}
		}

		swap(nums[left], nums[start]);
		
		sortQuick(nums, left, end - 1);
		sortQuick(nums, end + 1, right);
	}
	
	void sortQuick1(vector<int>& nums, int start, int end){
		if(start > end) return;
		int i = start;
		int j = end;
		// cout << "lefts:" << left << ",right:" << right << endl;
		while(i < j){
			
			while(i < j && nums[j] >= nums[start]){
				j--;
			}
			while(i < j && nums[i] <= nums[start]){
				i++;
			}
			
			if(i < j){
				swap(nums[i], nums[j]);

			}
		}

		swap(nums[start], nums[i]);
		
		sortQuick1(nums, start, j - 1);
		sortQuick1(nums, j + 1, end);
	}
	
	void sortBubble(vector<int>& nums){
		int len = nums.size();
		for(int i = 0; i < len - 1; i++){
			for(int j = 0; j < len - 1; j++){
				if(nums[j] > nums[j + 1]){
					swap(nums[j], nums[j + 1]);
				}
			}
		}
	}
	
	void sortSelect(vector<int>& nums){
		int len = nums.size();
		for(int i = 0; i < len - 1; i++){
			for(int j = i + 1; j < len; j++){
				if(nums[j] < nums[i]){
					swap(nums[j], nums[i]);
				}
			}
		}
	}
	
	void show(vector<int>& nums){
		for(auto i : nums){
			cout << i << ",";
		}
		cout << endl;
	}
};

int main(){
	Solution so;
	vector<int> nums = {0,0,2,2,1,1,2,0};
	so.sortColors(nums);
	so.show(nums);
	
	return 0;
}